﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    /// <summary>
    /// 有效的括号
    /// </summary>
    public class ValidParentheses : IRun
    {
        public void Run()
        {
            Method2("");
        }
        public bool Method1(string s)
        {
            Stack<char> _Stack = new Stack<char>();
            Dictionary<char, char> keyValuePairs = new Dictionary<char, char>()
            {
                {'(',')' },{'[',']' },{'{','}' }
            };

            for (int i = 0; i < s.Length; i++)
            {
                if (keyValuePairs.ContainsKey(s[i]))
                {
                    // (,[,{
                    _Stack.Push(s[i]);
                }
                else // ),],}
                {
                    if (_Stack.Count <= 0)
                        return false;

                    if (keyValuePairs[_Stack.Peek()] == s[i])
                    {
                        _Stack.Pop();
                    }
                    else
                    {
                        return false;
                    }
                }
            }

            if (_Stack.Count > 0)
                return false;
            else
                return true;
        }


        public bool Method2(string s)
        {
            Stack<char> Queue = new Stack<char>();
            Dictionary<char, char> keyValuePairs = new Dictionary<char, char>()
            {
                {'(',')' },{'[',']' },{'{','}' }
            };

            for (int i = 0; i < s.Length; i++)
            {
                if (Queue.Count <= 0)
                {
                    Queue.Push(s[i]);
                    continue;
                }

                if (!keyValuePairs.ContainsKey(Queue.Peek()))
                {
                    return false;
                }

                if (keyValuePairs[Queue.Peek()] == s[i])
                {
                    Queue.Pop();
                }
                else
                {
                    Queue.Push(s[i]);
                }
            }

            if (Queue.Count > 0)
                return false;
            else
                return true;
        }


    }
}
